Tempo Polinomial Aleatorizado (em inglês, Randomized polynomial time: RP) é uma classe de complexidade da complexidade computacional, problemas para nos quais a Máquina de Turing probabilística possui as seguintes propriedades:

• Sempre roda em tempo polinomial no tamanho da entrada
• Se a resposta correta é NÃO, ele sempre retorna NÃO
• Se a resposta correta for SIM, então ele tem uma probabilidade de 1/2 de retornar SIM (caso contrario, retorna NÃO).

Em outras palavras, o algoritmo permite jogar uma moeda realmente aleatória enquanto está rodando. O único caso no qual o algoritmo pode retornar SIM é quando a resposta é realmente SIM; portanto se o algoritmo termina e produz SIM, então a resposta correta é definitivamente SIM; entretanto, o algoritmo pode terminar com NÃO independentemente da verdadeira resposta. Ou seja, se o algoritmo retornar NÃO, ele pode estar errado.

Alguns autores chamam essa classe de R, entretanto esse nome é mais comumente usado para a classe das linguagens recursivas.

Se a resposta correta é SIM e o algoritmo for executado n vezes com o resultado de cada execução estatisticamente independente dos outros, então ele vai retornar SIM pelo menos uma vez com uma probabilidade de pelo menos 1 − 2⁻ⁿ. Logo, se o algoritmo executar 100 vezes, então a chance dele retornar a resposta errada todas as vezes é menor do que a chance de que raios cósmicos corrompam a memória do computador que esteja rodando o algoritmo. Dessa forma, se a fonte dos números aleatórios estiver disponível, a maior parte dos algoritmos em RP são altamente práticos.

A fração 1/2 na definição é arbitraria. O conjunto RP conterá exatamente os mesmos problemas, mesmo que 1/2 seja substituída por qualquer probabilidade constante diferente de zero e menor que 1; aqui constante significa independência da entrada do algoritmo.